// https://www.lintcode.com/problem/sort-colors/

public class Solution {
    /**
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     */
    public void sortColors(int[] nums) {
        // write your code here
        /*
        如果没有0，1可以在第0个位置出现。
        如果只有1个2，2出现在最后一个位置
        */
        int onePos = 0; // 1开始的位置
        int twoPos = nums.length - 1; // 2开始的位置
        int i = 0;
        while (i <= Math.min(twoPos, nums.length - 1)) {
            if (nums[i] == 0) {
                if (i == onePos) { // 1的位置要往后，但是这里先记录一下。
                    ++i;
                } else {
                    swap(nums, i, onePos); // 如果有1就把1放到指定位置
                }
                ++onePos;
            } else if (nums[i] == 2) {
                swap(nums, i, twoPos);
                --twoPos;
            } else {
                ++i;
            }
        }        
    }

    protected void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}